home *** CD-ROM | disk | FTP | other *** search
/ Delphi Magazine Collection 2001 / Delphi Magazine Collection 20001 (2001).iso / DISKS / Issue59 / ALFRESCO / TestPower.dpr < prev   
Encoding:
Text File  |  2000-06-05  |  1.2 KB  |  51 lines
  1. program TestPower;
  2.  
  3. {$APPTYPE CONSOLE}
  4.  
  5. uses
  6.   SysUtils;
  7.  
  8. function PowerAndMod(a, e, n : integer) : integer;
  9. {-calculate a^n mod n}
  10. var
  11.   Exponent : integer;
  12.   BitCount : integer;
  13.   i        : integer;
  14. begin
  15.   {reverse the bits in e and put them in Exponent}
  16.   Exponent := 0;
  17.   for i := 1 to 32 do begin
  18.     if Odd(e) then
  19.       Exponent := (Exponent shl 1) or 1
  20.     else
  21.       Exponent := (Exponent shl 1);
  22.     e := e shr 1;
  23.   end;
  24.   {pop off the clear bits until we reach the first set bit; this will
  25.    be the most significant bit of the original exponent}
  26.   BitCount := 32;
  27.   while not Odd(Exponent) do begin
  28.     Exponent := Exponent shr 1;
  29.     dec(BitCount);
  30.   end;
  31.   {OK, we're ready for the loop}
  32.   Result := 1;
  33.   {for all the bits in the original exponent...}
  34.   for i := pred(BitCount) downto 0 do begin
  35.     {sqaure the intermediate result}
  36.     Result := (Result * Result) mod n;
  37.     {if the current bit is set, multiply by a}
  38.     if Odd(Exponent) then
  39.       Result := (Result * a) mod n;
  40.     Exponent := Exponent shr 1;
  41.   end;
  42. end;
  43.  
  44. begin
  45.   writeln(PowerAndMod(3, 3, 437));
  46.   writeln(PowerAndMod(53, 17, 437));
  47.   writeln(PowerAndMod(318, 233, 437));
  48.  
  49.   readln;
  50. end.
  51.